Three classes of routing algorithm are established for Cray Inc. Dragonfly networks, minimal, non-minimal, and adaptive. They were developed as part of the Cascade project of Cray Inc. The minimal routing algorithm is optimal for traffic which is known to be uniformly distributed—each node communicates roughly equal amounts of data with all of the other nodes. The minimal routing algorithm is known not to be optimal for so called “worst case” traffic patterns in which all of the nodes in one group communicate exclusively with nodes in one other group. Non-minimal routing is known to perform better on such communication patterns; it distributes traffic over all groups, and from there to die destination. This approach is fair, but imposes a higher load (up to 2×) on the network. FIG. 1 shows a system 10 comprising multiple groups of nodes in which each of the groups of nodes 12 is connected to all of the others (illustrated by the lines between groups of nodes). Where traffic is uniformly distributed all paths are equally loaded as shown on the left hand side of the Figure. Where traffic is between pairs of groups of nodes 12 (shown in heavier lines on the right hand side of the Figure) many of the links are unused (thinner lines) with minimal routing. Adaptive routing algorithms select between minimal and non-minimal routing according to network load. This choice can be biased to favor minimal or non-minimal routing, for example, so that minimal routing can be preferred when the load is lower.
In general, global communication patterns (all-to-all or FFT for example) perform well with minimal routing and local-communication patterns (nearest neighbor for example) perform well with non-minimal (or some element of non-minimal) routing. However, the best routing algorithm for a given application is not generally known in advance. An application that exhibits uniform behavior over a long period of time may not do so over short periods. An application may use local communication in one phase and non-local in another. A good default algorithm is desired.